package leetcode.LinkedList;

/**
 * @author MaoLin Wang
 * @date 2020/2/1016:10
 */
public class _21MergeTwoLists {
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;

        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    public static ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        ListNode newNode = new ListNode(-1);
        ListNode temp1 = l1, temp2 = l2, temp = newNode;

        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        temp.next = temp1 == null ? temp2 : temp1;
        return newNode.next;
    }

    public static ListNode mergeTwoLists3(ListNode l1, ListNode l2) {
        if (l1==null){
            return  l2;
        }
        if (l2== null){
            return  l1;
        }
        ListNode t1=l1;
        ListNode t2=l2;
        ListNode res=new ListNode(-1);
        ListNode resTemp=res;
        while (t1!=null && t2!=null){
            if (t1.val <= t2.val){
                resTemp.next = t1;
                t1=t1.next;
            }else {
                resTemp.next=t2;
                t2=t2.next;
            }
            resTemp=resTemp.next;
        }
        if (t1!=null){
            resTemp.next=t1;
        }
        if (t2!=null){
            resTemp.next=t2;
        }
        return res.next;
    }



    public static ListNode mergeTwoListsTest(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }

        ListNode result = new ListNode(-1);
        ListNode tempRes = result;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tempRes.next = list1;
                list1 = list1.next;
            } else {
                tempRes.next = list2;
                list2 = list2.next;
            }
            tempRes = tempRes.next;
        }
       /* while (list1!=null){
            tempRes.next=list1;
            list1=list1.next;
            tempRes=tempRes.next;
        }
        while (list2!=null){
            tempRes.next=list2;
            list2=list2.next;
            tempRes=tempRes.next;
        }*/
        tempRes.next = list1 == null ? list2 : list1;
        return result.next;

    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(0);
        l1.next = new ListNode(1);
        l1.next.next = new ListNode(3);
        l1.next.next.next = new ListNode(4);
        l1.next.next.next.next = new ListNode(4);

        ListNode l2 = new ListNode(0);
        l2.next = new ListNode(2);
        l2.next.next = new ListNode(3);
        l2.next.next.next = new ListNode(5);
        l2.next.next.next.next = new ListNode(6);

        ListNode node = mergeTwoListsTest(l1, l2);
        ListNode.printNode(node);
    }
}
